package arrays;

import java.util.HashMap;
import java.util.Map;

/**
 * 题目：
 *  给定一个数组arr，返回arr的最长无重复子数组的长度(无重复指的是所有数字都不相同)。
 * @Author Gavin
 * @date 2022.08.06 17:27
 */
public class array_24 {
    /**
     解题思路：
     *      用一个map来存key，需要把数组下标记录下来，需要注意的有两点，一个就是如果找到一个重复元素了那么外层下标就可以从
     *      第一个重复元素重新开始计算，这样可以大大提升性能，还有如果内层循环到末尾了就可以直接返回，因为已经是最大的了
     *
     *      与动态规划中求最长无重复字符串长度的思路一样
     */
    public static int solution(int[] arr) {
        if(arr==null) return 0;
        if(arr.length==1) return 1;
        int max = 0;
        Map<Integer,Integer> map = new HashMap<>();
        int leftIndex = 0;
        int len = arr.length;
        while(leftIndex<len){
            int repeatData = -1;
            for(int i=leftIndex;i<len;i++){
                if(map.containsKey(arr[i])){
                    repeatData = arr[i];
                    break;
                }
                map.put(arr[i],i);
            }
            if(repeatData==-1){
                //说明没有遇到重复数据，一直到尾巴，这时就已经产生最大值了，
                //没必要继续了
                return Math.max(max,map.size());
            }else{
                //遇到了重复数据，但还没到尾巴，最大值不确定，需要继续
                //左界限指针直接跳到重复元素(第1个)的后面
                leftIndex = map.get(repeatData)+1;
                max = Math.max(max,map.size());
                map.clear();
            }
        }

        return max;
    }
}
